<script>
  // 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

  // 输入：l1 = [1,2,4], l2 = [1,3,4]
  // 输出：[1,1,2,3,4,4]

  // **** 题源：leetcode 21 https://leetcode.cn/problems/merge-two-sorted-lists/

  /**
   * 分析🔥
   * 设置一个哨兵 dummy （用于存放合并的链表） 一个指针 cur （用与跟踪当前的值 把值存上）
   * 如果 list1 和 list2 都不为null 的情况下
   * 进行 while 循环 条件是 list1 !== null && list2 !== null
   * 然后判断 list1.val < list2.val
   * 是的话存放小的值 然后 cur 指针指向下一个节点 ， 满足条件的链条 list1 or list2 也要指向下个节点
   * 也就是 cur.next  lsit1.next  list2.next 啦~~
   */

  /**
   * Definition for singly-linked list.
   * function ListNode(val, next) {
   *     this.val = (val===undefined ? 0 : val)
   *     this.next = (next===undefined ? null : next)
   * }
   */
  /**
   * @param {ListNode} list1
   * @param {ListNode} list2
   * @return {ListNode}
   */
  var mergeTwoLists = function (list1, list2) {
    var dummy = new ListNode(0); // 设置一个哨兵节点 返回的合并链表数据就存放在这里
    var cur = dummy; // 维护一个指针
    // list1 或者 list2 为空的时候 停止
    while (list1 !== null && list2 !== null) {
      if (list1.val < list2.val) {
        cur.next = list1;
        list1 = list1.next;
      } else {
        cur.next = list2;
        list2 = list2.next;
      }
      cur = cur.next; // 移动指针存放的位置
    }
    // 比较到最后有一种 情况 就是先有一边指向 null 处理最后的合并 把最后一个直接
    // list1 如果为null  说明 list2 还存在 否侧 就是 list1
    cur.next = list1 === null ? list2 : list1;
    return dummy.next; // 一开始存放了一个初始值0 所以要next
  };
</script>
